1. Field of the Invention
The present invention relates to the information processing of verifying the integrity of electronic data.
2. Description of the Related Art
Digital signature and message authentication code (MAC) are known as techniques of preventing alteration of data and verifying the integrity of data.
Digital signature is a technique of generating signature data for verifying integrity based on a public key cryptosystem. This technique is also called “electronic signature”. Signature data is generated by generating the hash value (also called the message digest) of data as a signature target using a hash function and encrypting the hash value with its private key. When performing signature verification, this system decrypts the signature data with the public key and compares the decryption result with the hash value generated from the signature target data. If they match each other, the technique determines that the signature is authenticated. Typical digital signature algorithms are RSA (Rivest Shamir Adleman) and DSA (digital signature algorithm).
A hash function is a one-way function of generating data (hash value) of a predetermined size from data of an arbitrary size. In particular, features of a hash value are that it is difficult to obtain other data from which the hash value is obtained and it is difficult to obtain two different data from which the same hash values are obtained. Typical hash functions are MD5 (message digest algorithm 5), SHA1 (secure hash algorithm 1), SHA2 (secure hash algorithm 2), and the like.
A message authentication code is signature data (also sometimes called a MAC value) for verifying integrity using a common key. There are HMAC (hash-based MAC) using a hash function, CMAC (cipher-based MAC) using a block cipher, and the like.
Japanese Patent No. 4576936 (literature 1) discloses a technique of verifying the integrity of data by adapting the above digital signature technique. This technique solves the problem of taking much time to perform verification with a current increase in data amount when verifying the integrity of contents (data) recorded on a recording medium. The technique disclosed in literature 1 fragments a content and generates and verifies signature data of each fragmented data. In signature verification, when the verification of fragmented data has succeeded, the technique determines that the verification of the integrity of the content has succeeded. That is, performing parallel processing of fragmented data will speed up verification.
As an information processing environment, a parallel processing environment has become general owing to the trend to a multicore CPU and the use of GPU (graphics processing unit) as image processing accelerators for general-purpose calculation.
Digital signature includes a hash function. A hash function is the recursive sequential processing of repetitively inputting the processing result obtained on the preceding stage to the subsequent stage, and hence is difficult to speed up by parallel processing. Note that the scheme disclosed in literature 1 fragments data and separately verifies each fragmented data, and hence can speed up the processing by independently and parallelly processing fragmented data. In other words, this technique verifies each fragmented data, and signature data is a set of signature data for each fragmented data. That is, this technique uses signature data different from that used by a general scheme of collectively processing overall data.